/*
提交链接:https://leetcode.cn/problems/best-sightseeing-pair/description/
1014. 最佳观光组合
赖德檀 2024/12/19
*/

class Solution {
public:
// values[i]+i+values[j]−j==values[i]+i 和 values[j]−j
// 由于 values[j]−j 是固定不变的
// 等价于求 [0,j−1] 中 values[i]+i 的最大值 mx
    int maxScoreSightseeingPair(vector<int>& values) {
        int ans = 0, mx = values[0] + 0;
        for (int i = 1; i < values.size(); ++i) {
            ans = max(ans, mx + values[i] - i);
            // 边遍历边维护
            mx = max(mx, values[i] + i);
        }
        return ans;
    }
};